package com.mlh.dp.knapsackProblem;
// 给定一个字符串 s 和一个字符串字典 wordDict ，在字符串 s 中增加空格来构建一个句子，
// 使得句子中所有的单词都在词典中。以任意顺序 返回所有这些可能的句子。
// 注意：词典中的同一个单词可能在分段中被重复使用多次。

// 输入:s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
// 输出:["pine apple pen apple","pineapple pen apple","pine applepen apple"]
// 解释: 注意你可以重复使用字典中的单词。


import java.util.*;

//读题思路：相对于单词拆分  单词拆分返回的true或者false
//而单词拆分II 他返回的是字典能够组成s 有几种方式
//完全背包的顺序问题
//暂时超过水平
public class WordSplitII {

    public List<String> method1(String s, List<String> wordDict) {
        HashSet<String> set = new HashSet<>(wordDict);
        int[]dp=new int[s.length()+1];
        dp[0]=1;
        for(int i=1;i<=s.length();++i){
            for(int j=1;j<=i;++j){
                if(set.contains(s.substring(j-1,i-1))){
                    dp[i]++;
                    dp[i]=dp[j]*dp[i];
                }
            }
        }
    return null;
    }


}
